package string;

/**
 * @author: june
 * @date: 2023/8/10
 * @description: 1071. 字符串的最大公因子
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 * <p>
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 **/

public class GCDOfStrings_1071 {
    /** 如果str1和str2有最大公约数，假设str1 = mGCD， str2 = nGCD，则str1 + str2 = （m+n）GCD = str2+str1
     * 所以可以判断出如果str1 + str2 != str2+str1，就没有最大公约数
     *
     * 如果2个字符串有最大公约数字符串，可以转换成求字符串长度的最大公约数
     */
    public String gcdOfStrings(String str1, String str2) {
        if (!str1.concat(str2).equals(str2.concat(str1))) {
            return "";
        }

        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    // 辗转相除法求最大公约数
    private int gcd(int a, int b) {
        int remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
}
